MPRI - Parisian Master of Research in Computer Science <br />Course 2.11.1: Approximation Algorithms, Randomization & Nature Programming <br />Nicolas SCHABANEL, CNRS - Université Paris Diderot <br /> <br />LECTURE 2 (2016/09/21) <br />MATHEMATICAL PROGRAMMING 1: LINEAR PROGRAMMING <br /> <br />[0:00:00] 0. Mathematical Programming <br />[0:01:45] 1. Introduction to Linear Programming <br />[0:07:04] 2. First Example: Max-CUT as an Integer Program <br />[0:38:16] 3. LP Relaxation for Max-CUT & Randomized Rounding <br />[1:09:26] 4. Max-SAT: Random Assignment <br />[1:24:23] 5. Max-SAT: Randomized Rounding <br />[2:12:33] 6. Max-SAT: Combining both Algorithms into One <br />[2:23:37] 7. Exercises 2: Maximum Arc-Disjoint Paths (2)
